There are two main approaches for automatically generating conversational utterances. One is the composition approach, in which 
utterances are dynamically assembled using some composition procedure, e.g. grammar
rules.  The other method, called ``generation by selection'' is not as wide spread. In this method the task is to pick the appropriate utterance from a
corpus of possible utterances in the domain of the task. In this section we 
review previous work on these two approaches in order to situate our work. 

\subsection{Generation by composition for conversational agents}

Generation of natural language by composition is typically modelled using the pipeline
architecture proposed in~\cite{reiter97}. The pipeline includes the following modules: 
1) \emph{content determination} that involves determining the communicative goal, 
2) \emph{micro-planning} that involves deciding how to refer to objects and how to agregate the
information, and 3) \emph{surface realization} that finally selects the actual words 
and grammatical constructions to be used in the utterance. 

Current compositional approaches can be classified into rule-based and corpus-based approaches. 
Rule-based approaches require to hand-craft each of the three modules and usually require
extensive adaptation or re-construction when moved to a new task~\cite{reiter-dale-book}. 
In particular, the content determination module, which determines the communicative goals that
the system can have, has to be completely re-deployed for each new task~\cite{Reiter03,traum03b}. 
There exist microplanning~\cite{Krahmer12} and surface realization~\cite{gardent07} modules that are supposed to be  
domain independent however, in practice, conversational agent developers
report that adaptating their coverage to new tasks is as costly as constructing such modules from 
scratch~\cite{DeVault08b}. 

In order to tailor natural language generation modules more easily to new domains and tasks, several corpus-based approaches have been proposed. 
Statistical techniques have been used for adapting content selection~\cite{Duboue03,Lapata03}, microplanning~\cite{Walker07} and realization~\cite{Bangalore2000}
modules to particular domains. These approaches made evident the fact that the pipeline architecture for natural language generation is not appropriate given than there exist strong interactions between all the modules which need to be optimized together. Recent work has dropped the pipeline architecture and proposed the joint optimization of the generation process using reinforcement learning~\cite{Dethlefs11} and cost-based automated planning~\cite{garoufi11}. 
All of these approaches use significant amounts of linguistic and pragmatic knowledge that have to be manually annotated by experts in order to
make the natural language output they produce effective for the task. In this article, we propose to
use a method that also learns to generate natural language output from a
corpus but does not require any manual annotation of the corpus.


\subsection{Generation by selection for conversational agents}

Generation by selection aims to disminish the cost of development of conversational agents by directly selecting utterances from data. Nowadays, most systems that use the generation by selection approach use utterances authored by humans, and not real utterances used by people playing a role. This is the case for many different kinds of agents ranging from negotiating agents~\cite{leuski09} to virtual patients~\cite{kenny07}. 

In general, all generation by selection approaches use some stimulus (for instance, a question received from the user) to decide which utterance to select. Given this generic view, the selection task can be casted into a classification task in the following way. When a new stimulus arrives---e.g.,~a question---it is converted into a feature vector representation, compared to the vectors of the known stimulus---questions found in corpora---the best matching group of stimulus is identified and its reaction---its answer---is returned. The disadvantage of this approach is that it completely ignores the content of the reactions in the corpora. Later work proposes how to consider the reactions by matching the user's question to known answers and not to the known stimulus~\cite{leuski09,leuski11}. In this proposal, the selection task is viewed as an information retrieval problem, in which the content of the result, not the content of previous queries, is used to select the response to a new query. This later approach has been showned to perform better than the former in terms of relevance to the stimulus. 

The advantages of generation by selection are many. To start with, it affords the use of complex and human-like sentences. Moreover, the system may easily use recorded audio clips rather than speech synthesis and recorded video for animating avatars. Finally, no rule writing by a dialogue expert or manual annotations is needed. 
%The disadvantage reported by previous work on generation by selection is that the resulting dialogue may not be fully coherent~\cite{shawar03,shawar05,gandhe07b}. 

Even though selection approaches are getting reasonably good at finding a good reaction given an stimulus their common problem is still the global conversational coherence. For the conversational agents known as chatbots, it is often sufficient to talk about topics at a fairly shallow level, without requiring a lot of detailed task knowledge or knowledge of how some parts of a task relate to others~\cite{shawar03,shawar05}. This luxury is not available for a task oriented dialogue where the system is expected to perform a task or provide task-specific information. There are some domains that fall between these extremes, for instance negotiation about whether or not to adopt a proposal. In this case, there is definitely a task or set of tasks involved, but one does not necessarily require as detailed knowledge as is required to actually perform the task. Gandhe and Traum~\cite{gandhe07,gandhe07b} investigate several dialogue models for negotiating virtual agents that are trained on an unannotated human-human corpus. Orkin and Roy~\cite{Orkin2009} report severe coherence problems in task-oriented conversational agents that use generation by selection from a corpus of human-human interactions in a virtual restaurant. The method we propose uses an automated planner to guide the selection and then maintain the global coherence of the interaction. 

%In previous work, the selection approach to generation has only been used non task-oriented conversational agents such as negotiating agents~\cite{gandhe07}, question answering characters~\cite{leuski09}, and virtual patients~\cite{kenny07}. To the best of our knowledge, our method is the first one proposed for generation by selection for task-oriented agents.  

%Since virtual instructors need to have a plan in order to help a user perform a task our proposal uses this plan in order to obtain a globally coherent interaction in the following way. Our algorithm selects the instruction whose corresponding reaction maximizes the advance in the task plan according to the corpus. In the newxt section we describe how such reactions are calculated. 

